package com.yuxi.al.leercode;

/**
 * 找出两个数组的中位数
 * eg: arr1=[1,2,3] arr2=[2,3,4]
 * result res = (2+3)/2=2.5
 * Created by yuxi on 2017/3/29.
 */
public class FindMedianSortedArrays {
    public static void main(String[] ags) {
        int[] arr1 = {1,2,3};
        int[] arr2 = {4,5,6};
        double res = findMedianSortedArrays(arr1, arr2);
        System.out.println(res);

        System.out.println(findMedianSortedArrays1(arr1, arr2));
    }

    /**
     * 我的思路是这样的，现将两个数组复制到另外一个数组里面，当然在复制的过程中是排序的
     * 我理解这个的时间复杂度应该是o(Max(m,n)),空间复制度o(m+n)
     * <p>
     * 复制完了之后就需要对这个数组处理了，处理的思路是：分别两个指针n,m从两头开始往中间走，
     * 当m==n是就是中间元素  当m>n时 取两个元素的差值
     *
     * @param arr1 第一个数组
     * @param arr2 第二个数组
     * @return
     */
    private static double findMedianSortedArrays(int[] arr1, int[] arr2) {
        //在一个数组里面找到中位数
        if (arr1 == null && (arr2.length > 0 && arr2 != null)) {
            return findMid(arr2);
        }
        if (arr2 == null && (arr1.length > 0 && arr1 != null)) {
            return findMid(arr1);
        }
        //重新定义一个数组，长度为arr1 和arr2之和
        int[] arr3 = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;
        while (i < arr1.length && j < arr2.length) {
            //数组复制
            if (arr1[i] <= arr2[j]) {
                arr3[k++] = arr1[i++];
            } else {
                arr3[k++] = arr2[j++];
            }
        }
        //处理越界情况
        if (i >= arr1.length) {
            while (j < arr2.length)
                arr3[k++] = arr2[j++];
        }
        if (j >= arr2.length) {
            while (i < arr1.length)
                arr3[k++] = arr1[i++];
        }
        return findMid(arr3);
    }

    /**
     * 找中位数
     *
     * @param arr3 对应的数组
     * @return
     */
    private static double findMid(int[] arr3) {
        //在arr3中找到中位数
        int n = 0, m = arr3.length - 1;
        while (true) {
            if (n > m) {
                double tmp = (Double.parseDouble(String.valueOf(arr3[n])) +
                        Double.parseDouble(String.valueOf(arr3[m]))) / 2;
                return tmp;
            } else if (n == m) {
                return arr3[m];
            } else {
                n++;
                m--;
            }
        }
    }

    //////////leetcode 神的答案,知道是递归处理的，到最后还是没有看懂到底为什么呢？？？？/////////////


    public static double findMedianSortedArrays1(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
    }

    public static double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
        if (aStart > A.length - 1) return B[bStart + k - 1];
        if (bStart > B.length - 1) return A[aStart + k - 1];
        if (k == 1) return Math.min(A[aStart], B[bStart]);

        int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
        if (aStart + k / 2 - 1 < A.length) aMid = A[aStart + k / 2 - 1];
        if (bStart + k / 2 - 1 < B.length) bMid = B[bStart + k / 2 - 1];

        if (aMid < bMid)
            return getkth(A, aStart + k / 2, B, bStart, k - k / 2);// Check: aRight + bLeft
        else
            return getkth(A, aStart, B, bStart + k / 2, k - k / 2);// Check: bRight + aLeft
    }
}
